package homework;

/**
 * @Author Stringzhua
 * @Date 2024/2/4 16:39
 * description:扩容+定位
 * 已知有一个升序的数组,要求插入一个元素,该数组顺序依然是升序,比如:
 * [10,12,45,90],添加23后,数组为[10,12,23,45,90]
 */
public class homework04 {
    public static void main(String[] args) {
        /*
         * 思路:
         * 1.先确定添加数应该插入到哪个索引
         * 2.然后扩容
         * */

        //先定义原数组
        int[] arr = {10, 12, 45, 90};
        int insertNum = -1;
        int index = 111;//index就是要插入的位置

        //遍历 arr数组,如果发现insertNum<arr[i],说明i就是要插入的位置
        //使用index保留index=i;
        //如果遍历完后,没有发现条件值insertNum<=arr[i],说明index=arr.length
        //即:添加到arr的最后
        for (int i = 0; i < arr.length; i++) {
            if (insertNum <= arr[i]) {
                index = i;
                break;//找到位置后,就退出
            }
        }
        //判断index的值
        if (index == -1) {//说明没有找到位置
            index = arr.length;
        }
        System.out.println("index = " + index);

        //扩容
        //先创建一个新的数组,大小arr.length+1
        int[] arrNew = new int[arr.length + 1];
        //先将arr的元素拷贝到arrNew,并且跳过index这个位置
        /*
         * 分析:
         * int[] arr={10,12,45,90}
         * arrNew={}
         * i控制arrNew的下标
         * j用来控制arr数组的下标
         * */
        for (int i = 0, j = 0; i < arrNew.length; i++) {
            if (i != index) {
                arrNew[i] = arr[j];
                j++;
            } else {//i这个位置就是要插入的数
                arrNew[i] = insertNum;
            }
        }
        //让arr指向arrNew,原来的数组,就成为垃圾,被销毁
        arr=arrNew;
        System.out.println("===插入后arr数组的情况===");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
